package pen_exam.zijie_2024_03_17;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;


//给定一个长度为2N的数组，每两个坐标可以任意做x和y
//求一个和坐标轴平行的矩形 包含所有的坐标
//问矩形的最小面积
public class Code02_MinS {
    //解1：将数组平均分为两个数组，求|xn-x1|*|yn-y1|的最小值
    public static int minS(int[] arr){
       if(arr == null || arr.length == 0){
           return 0;
       }
        ArrayList<Integer> xpath = new ArrayList<>();
        ArrayList<Integer> ypath = new ArrayList<>();
        Arrays.sort(arr);
       return process(arr,0,xpath,ypath);
    }
    //优化思路：1.折半查找：target 2.dp ： path，S
    //dp优化思路： xmax - xmin ymax - ymin xsize
    public static int process(int[] arr,int index,ArrayList<Integer> xpath,ArrayList<Integer> ypath){
       if(index == arr.length){
           if(xpath.size() == arr.length/2 && ypath.size() == arr.length/2){
               return Math.abs( (xpath.get(0) - xpath.get(xpath.size() - 1)) * (ypath.get(0) -ypath.get(ypath.size() - 1)));
           }else{
               return Integer.MAX_VALUE;
           }
       }
        ypath.add(arr[index]);
        int p1 = process(arr, index + 1, xpath, ypath);
        ypath.remove(ypath.size() - 1);
        xpath.add(arr[index]);
        int p2 = process(arr, index + 1, xpath, ypath);
        xpath.remove(xpath.size() - 1);
        return Math.min(p1, p2);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,2,4};
        System.out.println(minS(arr));
    }
}
